#
# @lc app=leetcode.cn id=1438 lang=python3
#
# [1438] 绝对差不超过限制的最长连续子数组
#

# @lc code=start
from typing import List
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        # print('haha')
        # import sortedcontainers
        # store = sortedcontainers.SortedList()
        # l, r, n = 0, 0, len(nums)
        # ans = 0
        # while r<n:
        #     store.add(nums[r])
        #     while store[-1]-store[0]>limit:
        #         store.remove(nums[l])
        #         l+=1
        #     r+=1
        #     ans = max(ans, r-l)
        # return ans

        import collections
        maxque = collections.deque()
        minque = collections.deque()
        l, r, n = 0, 0, len(nums)
        ans=0
        while r<n:
            while maxque and nums[r]>maxque[-1]:
                maxque.pop()
            maxque.append(nums[r])
            while minque and nums[r]<minque[-1]:
                minque.pop()
            minque.append(nums[r])
            while maxque and minque and maxque[0]-minque[0]>limit:
                if maxque[0]==nums[l]:
                    maxque.popleft()
                if minque[0]==nums[l]:
                    minque.popleft()
                l+=1
            r+=1
            ans = max(ans, r-l)
            # print(l, r, minque, maxque, ans)

        return ans


# @lc code=end

if __name__=='__main__':
    solution = Solution()
    nums = [4,2,2,2,4,4,2,2]
    limit = 0
    print(solution.longestSubarray(nums, limit))
